package com.c2b.algorithm.leetcode.base;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/count-distinct-numbers-on-board/'>统计桌面上的不同数字(Count Distinct Numbers on Board)</a>
 * <p>
 * 给你一个正整数 n ，开始时，它放在桌面上。在 10^9 天内，每天都要执行下述步骤：
 *     <ul>
 *         <li>对于出现在桌面上的每个数字 x ，找出符合 1 <= i <= n 且满足 x % i == 1 的所有数字 i 。</li>
 *         <li>然后，将这些数字放在桌面上。</li>
 *     </ul>
 * </p>
 * <p>返回在 10^9 天之后，出现在桌面上的 不同 整数的数目。</p>
 * <p>
 *     注意：
 *     <ul>
 *         <li>一旦数字放在桌面上，则会一直保留直到结束。</li>
 *         <li>% 表示取余运算。例如，14 % 3 等于 2 。</li>
 *     </ul>
 * </p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：n = 5
 *      输出：4
 *      解释：最开始，5 在桌面上。
 *          第二天，2 和 4 也出现在桌面上，因为 5 % 2 == 1 且 5 % 4 == 1 。
 *          再过一天 3 也出现在桌面上，因为 4 % 3 == 1 。
 *          在十亿天结束时，桌面上的不同数字有 2 、3 、4 、5 。
 *
 * 示例 2：
 *      输入：n = 3
 *      输出：2
 *      解释：
 *          因为 3 % 2 == 1 ，2 也出现在桌面上。
 *          在十亿天结束时，桌面上的不同数字只有两个：2 和 3 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= n <= 100</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/24 16:20
 */
public class LC2549CountDistinctNumbersOnBoard_S {

    static class Solution {

        public int distinctIntegers(int n) {
            // 如果 n 是偶数，则会把所有除 1 之外的奇数都加上
            // 如果 n 是奇数，则会把所有除 1 之外的偶数都加上
            // 总的来说：如果是1，则只有1个；如果不为1，则除1之外的数都会出现一次
            return n == 1 ? 1 : n - 1;
        }

        public int distinctIntegers2(int n) {
            // 所有的卡片
            Set<Integer> allDistinctIntegers = new HashSet<>();
            // 今天的卡片
            Set<Integer> todayDistinctIntegers = new HashSet<>();
            todayDistinctIntegers.add(n);
            while (!todayDistinctIntegers.isEmpty()) {
                // 产生的新的卡片，作为明天要处理的卡片
                Set<Integer> tempSet = new HashSet<>();
                for (Integer integer : todayDistinctIntegers) {
                    for (int i = 1; i <= integer; i++) {
                        if (integer % i == 1) {
                            tempSet.add(i);
                        }
                    }
                    allDistinctIntegers.add(integer);
                }
                todayDistinctIntegers = tempSet;
            }
            return allDistinctIntegers.size();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.distinctIntegers(5));
        System.out.println(solution.distinctIntegers(3));
    }
}
